//leetcode_36:有效的数独
//请你判断一个9 x 9 的数独是否有效。只需要 根据以下规则 ，验证已经填入的数字是否有效即可。
//        数字1-9在每一行只能出现一次。
//        数字1-9在每一列只能出现一次。
//        数字1-9在每一个以粗实线分隔的3x3宫内只能出现一次。（请参考示例图）
//        注意：
//        一个有效的数独（部分已被填充）不一定是可解的。
//        只需要根据以上规则，验证已经填入的数字是否有效即可。
//        空白格用'.'表示。
//输入：board =
//        [["5","3",".",".","7",".",".",".","."]
//        ,["6",".",".","1","9","5",".",".","."]
//        ,[".","9","8",".",".",".",".","6","."]
//        ,["8",".",".",".","6",".",".",".","3"]
//        ,["4",".",".","8",".","3",".",".","1"]
//        ,["7",".",".",".","2",".",".",".","6"]
//        ,[".","6",".",".",".",".","2","8","."]
//        ,[".",".",".","4","1","9",".",".","5"]
//        ,[".",".",".",".","8",".",".","7","9"]]
//        输出：true


import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

public class leetcode_36 {

    public boolean isValidSudoku(char[][] board) {
//        直观上，我们很容易想到使用 哈希表 来记录某行/某列/某个小方块出现过哪些数字，来帮助我们判断是否符合「有效数独」的定义。
            Map <Integer, Set <Integer>> row  = new HashMap <>(), col = new HashMap<>(), area = new HashMap<>();
            for (int i = 0; i < 9; i++) {
                row.put(i, new HashSet<>());
                col.put(i, new HashSet<>());
                area.put(i, new HashSet <>());
            }
            for (int i = 0; i < 9; i++) {
                for (int j = 0; j < 9; j++) {
                    char c = board[i][j];
                    if (c == '.') continue;
                    int u = c - '0';
//                  然后推导出小方块编号和行列的关系
                    int idx = i / 3 * 3 + j / 3;
                    if (row.get(i).contains(u) || col.get(j).contains(u) || area.get(idx).contains(u)) return false;
                    row.get(i).add(u);
                    col.get(j).add(u);
                    area.get(idx).add(u);
                }
            }
            return true;
        }


}
